package com.wengu.sort;

import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @author whl
 * @Description
 * @date 2021/7/6 11:20
 * @Version 1.0
 */
public class MergeSortDemo {
    int count = 0;

    @Test
    public void test(){
        int arr[] = {44,42,35,28,23,17,9,6,1};
        int[] temp = new int[arr.length];
        mergeSort(arr,0,arr.length - 1,temp);
        System.out.println("归并排序后的数组：" + Arrays.toString(arr));
    }

    public void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            // 左边递归
            mergeSort(arr, left, mid, temp);
            // 右边递归
            mergeSort(arr, mid + 1, right, temp);
            // 合并
            merge(arr,left,mid,right,temp);
        }
    }

    /**
     * 合并
     *
     * @param arr   原数组
     * @param left  最左边的索引
     * @param mid   中间索引
     * @param right 最右边的索引
     * @param temp  临时数组
     */
    public void merge(int[] arr, int left, int mid, int right, int[] temp) {
        // 将原数组拆分为两个有序数组，并将这两个有序数组按照从小到大的顺序依次放入临时数组
        int l = left; // 左边列表的索引
        int r = mid + 1; // 右边列表的索引
        int tempIndex = left; // 临时数组的索引
        while (l <= mid && r <= right) {
            if (arr[l] <= arr[r]) {
                temp[tempIndex] = arr[l];
                l++;
            } else {
                temp[tempIndex] = arr[r];
                r++;
            }
            tempIndex++;
        }
        while (l <= mid) {
            temp[tempIndex] = arr[l];
            l++;
            tempIndex++;
        }
        while (r <= right) {
            temp[tempIndex] = arr[r];
            r++;
            tempIndex++;
        }

        // 将临时数组的数据拷贝到原数组中
        for (int i = left; i <= right; i++) {
            arr[i] = temp[i];
        }
        count++;
        System.out.println("第"+count+"次合并后的结果为：" + Arrays.toString(arr));
    }

}
